package day_2022_4_to_7.nowcoder;

/**
 * 树的子结构
 * @author haomin
 * @date 2022/04/17 18:46
 **/
public class HasSubtree_14f {
    public boolean isSubtree(TreeNode root,TreeNode subRoot) {
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null || subRoot ==null){
            return false;
        }

        return isSameTree(root,subRoot) ||
                isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    //与（leetcode 100.相同的树） 有相似之处，
    // 但是此处当子链为空时，主链不一定为空
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果q为空说明子链已将比较完了，且都相等
        if(q == null){
            return true;
        }
        // 走到这，说明q子链不为空，p为空，表示q并不是p的子链
        if(p == null){
            return false;
        }
        return p.val==q.val && isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
    }
}